package com.java.search;

import java.util.ArrayList;
import java.util.List;

/**
 * 二分查找
 *
 * @author 19252
 * @date 2020/7/20
 */
public class BinarySearch {

    public static void main(String[] args) {
        BinarySearch binarySearch = new BinarySearch();
        // int[] array = new int[]{0, 1, 2, 8, 9};
        int[] array = new int[]{0,1,2,3,4,5,6,7,8,9};
        int[] array2 = new int[]{1, 1, 1, 2, 8, 9};
        System.out.println(binarySearch.search(array, 0, array.length - 1, 1));
        // System.out.println(binarySearch.searchGetList(array2, 0, array2.length - 1, 2));

    }

    /**
     * 二分查找的先决条件是该序列是有序序列，在这里使用的是序列还要求是从小到大排列
     * 二分查找数据，存在返回下标，不存在返回 -1
     *
     * @param array 传入的数组
     * @param left  数组的左边界
     * @param right 数组的右边界
     * @param value 被查找的数的值
     * @return 返回值
     */
    public int search(int[] array, int left, int right, int value) {
        System.out.println("sawdawda");
        int l = left;
        int r = right;
        int mid = (left + right) / 2;
        // 首先判断划分出来的中点是否就是我们需要的值
        if (array[mid] == value) {
            // 是直接返回下标
            return mid;
        } else if (array[mid] < value) {
            // 并且当前数组分组不是只有一个数
            if (l < r) {
                return search(array, mid + 1, r, value);
            }
        } else if (array[mid] > value) {
            if (l < r) {
                return search(array, l, mid - 1, value);
            }
        }
        return -1;
    }


    /**
     * 进行扩展 返回所有的符合的下标
     * @param array 传入的数组
     * @param left  数组的左边界
     * @param right 数组的右边界
     * @param value 被查找的数的值
     * @return 返回保存符合条件的下标的集合
     */
    public List<Integer> searchGetList(int[] array, int left, int right, int value) {
        System.out.println("sawdawda");

        int l = left;
        int r = right;
        int mid = (left + right) / 2;
        // 首先判断划分出来的中点是否就是我们需要的值
        if (array[mid] == value) {
            // 找到符合条件的值，对值的左右进行扫描获取其它符合条件的值
            List<Integer> list = new ArrayList<>();
            // 向左查找
            int temp = mid - 1;
            while (temp >= 0){
                if (array[temp] == value){
                    list.add(temp);
                }else {
                    break;
                }
                temp --;
            }
            // 保存中间下标
            list.add(mid);
            // 遍历右边
            temp = mid + 1;
            while (temp < array.length){
                if (array[temp] == value){
                    list.add(temp);
                }else {
                    break;
                }
                temp ++;
            }
            return list;
        } else if (array[mid] < value) {
            // 并且当前数组分组不是只有一个数
            if (l < r) {
                return searchGetList(array, mid + 1, r, value);
            }
        } else if (array[mid] > value) {
            if (l < r) {
                return searchGetList(array, l, mid - 1, value);
            }
        }
        return null;
    }
}
